The present invention relates to random number generators, and more specifically, to utilizing timing jitter in generation of random generator numbers.
Random-number generation generally consists of two stages, short, unpredictable true random numbers (seeds) feeding fast, deterministic random number generators (also called pseudo-random number generators). The deterministic generators contribute no true randomness, but may improve statistical properties of the data stream. All non-predictability is derived from the initial seed. Therefore, the quality and throughput of entropy derived from a particular seed is critical.
A deterministic generator (often simply called an “extractor”) is a function which, when applied to a seed (such as radioactive decay, or thermal noise), generates a random output that may be shorter, yet uniformly distributed. In other words, outputting a completely random sample from a semi-random input. The goal of this process is to generate a truly random output stream, which could then be considered as being a true random number generator (TRNG).
In certain popular entropy extractors, raw information content (“entropy”) is extracted from measured timing differences. Measured timing differences shall be referred to generally a “jitter” or “clock jitter.” Thus, jitter is one seed from which random numbers may be generated.
Jitter is derived from frequent, periodic sampling of an unpredictable event source, typically a clock-derived source. Jitter sampling is usually done at the highest feasible frequency, because the sampling frequency limits the entropy extraction rate.
Jitter-based entropy extraction (i.e., using jitter as a seed) becomes inefficient as the variation in latency decreases because measurements of periodic events, being entirely predictable, contribute no entropy. Indeed, the amount of entropy extractable from a data stream is inversely related to its compressibility, and information related to periodic events may be compressed very efficiently.
In virtualized, timesliced environments, short-term variation of clock (or timer) jitter is generally negligible. Thus, extractable entropy bandwidth is severely limited. Each timesliced process owns its time intervals (timeslices) exclusively, without interference from other active processes. Within an exclusively owned timeslice, the process perceives an environment dedicated to its execution, and periodic sampling results in negligible variation due to the lack of interference. Indeed, in a typical timesliced environment, minimizing cross-process interference is an explicit design goal, which reduces a significant contribution to latency variance as a side effect.
In addition to the lack of inter-process interference, virtualization, especially clock virtualization, may further limit clock jitter. Virtualization separates observable events from their original sources, possibly reducing the entropy during translation. As an example, timer (or clock) virtualization transforms time snapshots of a real time source, remapping into a different time domain. If the virtualized timer is also quantized, which is typical, less entropy remains extractable than in the original source (as described above, quantization reduces entropy because it improves periodicity, therefore compressibility).
The only reliable, periodic interruption in such systems is related to timeslice-switching. Timeslice-switching occurs as a result of administrative operations during timeslicing and are not predictable to arbitrary precision. Essentially, timeslice switches are unpredictable events.
Unfortunately, timeslice switches, also referred to as “context switches” in this context,” are relatively infrequent. Indeed, a range of milliseconds is typical, containing tens of millions of (or considerably more) clock cycles within a timeslice. For this reason, it is impractical to use traditional, single-process entropy extractors in such an environment.